#include "headfiles.h"

using namespace std;

string addBinary(string a, string b) {
    string output;
    int size_a = a.size();
    int size_b = b.size();
    int i, j;
    int carry = 0;
    for (i = size_a - 1, j = size_b - 1; i >= 0 && j >= 0; i--, j--) {
        int da = a[i] - '0';
        int db = b[j] - '0';
        int d = da + db + carry;
        carry = d / 2;
        d = d & 1;
        output.push_back('0' + d);
    }
    
    for (; i >= 0; i--) {
        int da = a[i] - '0';
        int d = da + carry;
        carry = d / 2;
        d = d & 1;
        output.push_back('0' + d);
    }
    
    for (; j >= 0; j--) {
        int db = b[j] - '0';
        int d = db + carry;
        carry = d / 2;
        d = d & 1;
        output.push_back('0' + d);
    }
    
    if (carry) {
        output.push_back('1');
    }
    
    reverse(output.begin(), output.end());
    
    return output;
    
}

